Manacher's Algorithm

contents

Manacher's Algorithm은 문자열 내에서 가장 긴 팰린드롬 부분 문자열(Longest Palindromic Substring) 을 찾는 효율적인 알고리즘입니다.

보통 팰린드롬을 찾는 단순한 방법은 $O(N^2)$ 또는 $O(N^3)$의 시간이 걸리지만, Manacher 알고리즘은 $O(N)$ (선형 시간) 만에 이를 해결합니다.

1. 핵심 아이디어: "이미 아는 정보 재활용하기"

팰린드롬은 좌우 대칭이라는 특성이 있습니다.

만약 우리가 어떤 큰 팰린드롬 안에 있다면, 그 중심을 기준으로 왼쪽 편의 정보를 이용해 오른쪽 편의 정보를 계산하지 않고도 예측할 수 있지 않을까요?

이것이 Manacher 알고리즘의 핵심입니다.

"이미 검사한 영역(Center, Right Boundary) 내에서는 대칭성을 이용해 불필요한 비교를 건너뛴다."

2. 전처리 (Preprocessing): 짝수/홀수 길이 통일하기

팰린드롬은 길이가 홀수일 수도(aba), 짝수일 수도(abba) 있습니다.

• 홀수 길이: 중심이 문자 하나 (예: b)
• 짝수 길이: 중심이 문자 사이의 빈 공간 (예: b와 b 사이)

이 두 가지 경우를 따로 처리하려면 코드가 복잡해집니다. 이를 해결하기 위해 문자열의 모든 문자 사이사이에 특수 문자(예: #)를 끼워 넣습니다.

• 원본: aba $\rightarrow$ 변환: #a#b#a# (길이 7, 홀수)
• 원본: abba $\rightarrow$ 변환: #a#b#b#a# (길이 9, 홀수)

이렇게 하면 항상 홀수 길이의 문자열만 다루면 되므로 로직이 통일됩니다. (양 끝에 ^, $ 같은 다른 문자를 추가해 경계 검사를 생략하기도 합니다.)

3. 주요 변수 정의

알고리즘을 이해하기 위해 3가지 중요한 변수가 필요합니다.

1. $P[i]$: 변환된 문자열에서 인덱스 $i$를 중심으로 하는 팰린드롬 반지름의 길이입니다.
   • (자기 자신을 포함하거나 제외하는 정의가 다를 수 있지만, 보통 반지름이 $k$라면 팰린드롬의 총 길이는 $2k+1$이 됩니다. #를 포함해서요.)
2. $C$ (Center): 현재까지 발견된 팰린드롬 중, 가장 오른쪽까지 뻗어 나가는 팰린드롬의 중심 인덱스입니다.
3. $R$ (Right Boundary): 그 $C$를 중심으로 하는 팰린드롬의 가장 오른쪽 끝 인덱스입니다. ($R = C + P[C]$)

4. 알고리즘 동작 원리 (Case 분류)

우리는 $i$를 0부터 끝까지 진행하며 $P[i]$를 구하려고 합니다.

이때 $i$가 $R$ (현재 가장 오른쪽 경계)보다 안쪽에 있는지, 바깥쪽에 있는지에 따라 처리가 달라집니다.

Case 1: $i > R$ (경계 밖)

• $i$가 현재까지 알려진 팰린드롬 영역을 벗어났습니다.
• 우리는 $i$에 대한 정보가 전혀 없습니다.
• 동작: $i$를 중심으로 좌우를 하나씩 비교하며 $P[i]$를 0부터 직접 구해야 합니다(Brute Force).

Case 2: $i \le R$ (경계 안)

• $i$는 $C$를 중심으로 하는 거대한 팰린드롬 안에 속해 있습니다.
• 대칭성에 의해, $C$를 기준으로 $i$의 반대편에 있는 점 $i'$ (Mirror) 의 정보를 활용할 수 있습니다.
  • $i' = 2 \times C - i$
• 기본적으로 $P[i]$는 $P[i']$와 같을 가능성이 큽니다. 하지만 무조건 같지는 않습니다.

여기서 다시 세부 조건이 나뉩니다.

2-A. $P[i'] < R - i$ (Mirror가 경계 안쪽에 완벽히 포함될 때)

• $i'$의 팰린드롬이 $L$ (왼쪽 경계)을 넘어가지 않습니다.
• 대칭성에 의해 $i$의 팰린드롬도 $R$을 넘어가지 않습니다.
• 결과: $P[i] = P[i']$ (추가 비교 필요 없음!)

2-B. $P[i'] \ge R - i$ (Mirror가 경계 밖으로 걸칠 때)

• $i'$의 팰린드롬은 왼쪽 경계 $L$을 넘어갑니다.
• 하지만 $i$의 팰린드롬이 $R$을 넘어갈지는 확신할 수 없습니다. $R$ 이후의 문자는 아직 검사하지 않았기 때문입니다.
• 결과: 일단 $P[i]$를 $R - i$ (오른쪽 끝까지의 거리)로 초기화한 뒤, $R$ 바깥쪽 영역에 대해서만 추가로 비교를 수행합니다.

5. 값 갱신

$P[i]$를 구한 후, 만약 $i$를 중심으로 한 팰린드롬이 기존의 $R$보다 더 오른쪽으로 뻗어 나간다면 정보를 갱신합니다.

if (i + P[i] > R) {
    C = i;
    R = i + P[i];
}

이 과정 덕분에 $R$은 계속 오른쪽으로만 이동하거나 제자리에 있습니다. $R$이 문자열 끝까지 도달하면 알고리즘은 $O(N)$에 종료됩니다.

6. 구현 코드 (Java)

사용자분이 Java 개발자이시므로 Java로 구현해 보겠습니다.

public class Manacher {
    public String getLongestPalindromicSubstring(String s) {
        if (s == null || s.length() == 0) return "";

        // 1. 전처리: "abba" -> "^#a#b#b#a#$"
        // ^와 $는 경계 검사를 피하기 위한 센티널(Sentinel) 문자
        StringBuilder sb = new StringBuilder();
        sb.append('^');
        for (int i = 0; i < s.length(); i++) {
            sb.append('#').append(s.charAt(i));
        }
        sb.append("#$");
        String T = sb.toString();
        
        int n = T.length();
        int[] P = new int[n];
        int C = 0; // 중심 (Center)
        int R = 0; // 오른쪽 경계 (Right Boundary)

        // 2. 알고리즘 수행
        // i는 1부터 n-2까지 (센티널 제외)
        for (int i = 1; i < n - 1; i++) {
            int i_mirror = 2 * C - i; // C를 기준으로 i의 대칭점

            if (R > i) {
                // Case 2: R 안쪽에 있을 때
                // min(mirror의 값, R까지 남은 거리)
                P[i] = Math.min(P[i_mirror], R - i);
            } else {
                // Case 1: R 바깥에 있을 때
                P[i] = 0;
            }

            // 중심을 기준으로 확장 시도 (남은 영역 비교)
            while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i])) {
                P[i]++;
            }

            // 3. C와 R 갱신
            if (i + P[i] > R) {
                C = i;
                R = i + P[i];
            }
        }

        // 4. 최대 길이 찾기 및 원본 문자열 추출
        int maxLen = 0;
        int centerIndex = 0;
        for (int i = 1; i < n - 1; i++) {
            if (P[i] > maxLen) {
                maxLen = P[i];
                centerIndex = i;
            }
        }

        // 변환된 문자열에서 원본 인덱스로 변환
        // 시작 인덱스 계산: (중심 - 반지름) / 2
        int start = (centerIndex - maxLen) / 2;
        return s.substring(start, start + maxLen);
    }
}

7. 복잡도 분석

• 시간 복잡도: $O(N)$
  • 언뜻 보면 이중 루프(for 안에 while)가 있어 $O(N^2)$처럼 보일 수 있습니다.
  • 하지만 while 문(확장)은 $R$이 증가할 때만 실질적으로 반복됩니다.
  • $R$은 절대 줄어들지 않고 최대 문자열 길이만큼만 증가하므로, 전체 비교 횟수는 $N$에 비례합니다.
• 공간 복잡도: $O(N)$
  • 길이가 2배 늘어난 변환 문자열 $T$와 반지름 배열 $P$가 필요합니다.

요약

1. 문자열 사이사이에 #을 넣어 짝수/홀수 길이를 통일한다.
2. $P[i]$ 배열을 채우면서 진행한다.
3. 대칭성 활용: 현재 검사 중인 $i$가 가장 오른쪽 경계 $R$ 안에 있다면, 반대편 $i'$의 값을 가져와서 초기값으로 쓴다.
4. $R$을 넘어가는 부분만 추가로 비교한다.
5. 가장 큰 $P[i]$를 찾으면 그것이 가장 긴 팰린드롬이다.

예시 문자열 S = "babad"를 사용하겠습니다.

1. 전처리 (Preprocessing)

먼저 짝수/홀수 길이를 통일하기 위해 문자열을 변환합니다.

• 원본: b a b a d
• 변환 ($T$): ^ # b # a # b # a # d # $

인덱스 지도:

2. 트레이스 테이블 (Trace Table)

주요 변수 의미:

• $C$: 현재 가장 멀리 뻗은 팰린드롬의 중심 (Center).
• $R$: 그 팰린드롬의 오른쪽 경계 ($C + P[C]$).
• $i'$ (Mirror): $C$를 기준으로 한 $i$의 대칭점 ($2C - i$).
• 로직:
  • Case 1: $i > R$ (경계 밖 $\rightarrow$ 0부터 시작).
  • Case 2: $i \le R$ (경계 안 $\rightarrow$ $\min(P[i'], R - i)$ 사용).

(인덱스 11, 12는 생략했습니다. 로직은 동일합니다.)

3. 결과 분석

위에서 생성된 $P$ 배열을 살펴봅시다:

• 인덱스 2 (b): $P[2] = 1$ $\rightarrow$ 길이 $1 \times 2 + 1 = 3$ (#b#) $\rightarrow$ "b"
• 인덱스 4 (a): $P[4] = 3$ $\rightarrow$ 길이 $3 \times 2 + 1 = 7$ (#b#a#b#) $\rightarrow$ "bab"
• 인덱스 6 (b): $P[6] = 1$ $\rightarrow$ 길이 $3$ $\rightarrow$ "b"
• 인덱스 8 (a): $P[8] = 1$ $\rightarrow$ 길이 $3$ $\rightarrow$ "a" (#a#)
• 인덱스 10 (d): $P[10] = 1$ $\rightarrow$ 길이 $3$ $\rightarrow$ "d"

최종 승자: 반지름 3을 가진 인덱스 4.

가장 긴 팰린드롬: "bab" (참고: "aba"도 길이가 같아서 정답이 될 수 있지만, 보통 알고리즘은 먼저 발견된 것을 선택합니다).

4. "효율성(최적화)" 시각화

$i=6$ 일 때를 다시 봅시다:

• 현재 위치는 $i=6$ (b)입니다.
• 현재 중심 $C=4$ (a), 오른쪽 경계 $R=7$ (#)입니다.
• 우리는 경계 안에 있습니다 ($6 < 7$).
• 4를 기준으로 6의 대칭점(Mirror)은 2입니다.
• 우리는 2번 인덱스의 값을 2단계에서 이미 계산했습니다. $P[2] = 1$.
• 따라서 $P[6]$은 최소 1부터 시작한다는 것을 즉시 알 수 있습니다.
• b 바로 옆에 있는 문자들(#)을 다시 검사할 필요가 없습니다. 이미 대칭점에서 같다는 것을 확인했기 때문입니다. 우리는 그 반지름 너머 만 검사하면 됩니다.

이러한 "건너뛰기(Skipping)" 과정 덕분에 알고리즘이 $O(N^2)$이 아닌 $O(N)$의 속도를 낼 수 있습니다.

references